/*
    贪心经典题目专题6

    前置知识: 
    讲解005、042 - 对数器
    讲解025、026、027 - 基础排序、有序表、比较器、堆结构

    狭义的贪心
    每一步都做出在当前状态下最好或最优的选择，从而希望最终的结果是最好或最优的算法

    广义的贪心
    通过分析题目自身的特点和性质，只要发现让求解答案的过程得到加速的结论，都算广义的贪心

    贪心是最符合自然智慧的思想，一般分析门槛不高
    理解基本的排序、有序结构，有基本的逻辑思维就能理解
    但是贪心的题目，千题千面，极难把握
    难度在于证明局部最优可以得到全局最优，好在！我们有对数器！贪心专题2、3，这两节大量使用对数器

    ================================================

    有关贪心的若干现实 & 提醒
    1，不要去纠结严格证明，每个题都去追求严格证明，浪费时间、收益很低，而且千题千面。玄学！
    2，一定要掌握用对数器验证的技巧，这是解决贪心问题的关键
    3，解法几乎只包含贪心思路的题目，代码量都不大
    4，大量累积贪心的经验，重点不是证明，而是题目的特征，以及贪心方式的特征，做好总结方便借鉴
    5，关注题目数据量，题目的解可能来自贪心，也很可能不是，如果数据量允许，能不用贪心就不用（稳）
    6，贪心在笔试中出现概率不低，但是面试中出现概率较低，原因是 淘汰率 vs 区分度
    7，广义的贪心无所不在，可能和别的思路结合，一般都可以通过自然智慧想明白，依然不纠结证明

    ================================================

    题目1
    消灭怪物的最大数量
    你正在玩一款电子游戏，在游戏中你需要保护城市免受怪物侵袭
    给定两个大小为n的整数数组dist、speed
    其中dist[i]是第i个怪物与城市的初始距离
    其中speed[i]是第i个怪物的速度
    你有一种武器，一旦充满电，就可以消灭一个怪物，但是，武器需要1的时间才能充电完成
    武器在游戏开始时是充满电的状态，怪物从0时刻开始移动，一旦任何怪物到达城市，就输掉了这场游戏
    如果某个怪物恰好在某一分钟开始时到达城市，这也会被视为输掉游戏
    返回在你输掉游戏前可以消灭的怪物的最大数量，如果消灭所有怪兽了返回n
    测试链接 : https://leetcode.cn/problems/eliminate-maximum-number-of-monsters/

    ================================================

    题目2
    最大回文数字
    给你一个仅由数字（0 - 9）组成的字符串num
    请你找出能够使用num中数字形成的最大回文整数
    并以字符串形式返回，该整数不含前导零
    你无需使用num中的所有数字，但你必须使用至少一个数字，数字可以重新排列
    测试链接 : https://leetcode.cn/problems/largest-palindromic-number/

    ================================================

    题目3
    最大平均通过率
    一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试
    给你一个二维数组classes，其中classes[i]=[passi, totali]
    表示你提前知道了第i个班级总共有totali个学生
    其中只有 passi 个学生可以通过考试
    给你一个整数extraStudents，表示额外有extraStudents个聪明的学生，一定能通过期末考
    你需要给这extraStudents个学生每人都安排一个班级，使得所有班级的平均通过率最大
    一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数
    平均通过率 是所有班级的通过率之和除以班级数目
    请你返回在安排这extraStudents个学生去对应班级后的最大平均通过率
    测试链接 : https://leetcode.cn/problems/maximum-average-pass-ratio/

    本题和讲解091，题目3，组团买票问题很像，但是要简单很多

    ================================================
    
    题目4
    雇佣K名工人的最低成本
    有n名工人，给定两个数组quality和wage
    其中quality[i]表示第i名工人的工作质量，其最低期望工资为wage[i]
    现在我们想雇佣k名工人组成一个工资组
    在雇佣一组k名工人时，我们必须按照下述规则向他们支付工资：
    对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资
    工资组中的每名工人至少应当得到他们的最低期望工资
    给定整数k，返回组成满足上述条件的付费群体所需的最小金额
    测试链接 : https://leetcode.cn/problems/minimum-cost-to-hire-k-workers/

    本题和讲解092，题目4，知识竞赛问题很像，都是根据一个标准把样本进行排序
    然后按照排序后的顺序，逐一来到每个样本，计算在该样本参与的情况下，最佳答案是什么
    排序之后的顺序，可以起到加速计算的效果

    ================================================

    题目5
    砍树
    一共有n棵树，每棵树都有两个信息：
    第一天这棵树的初始重量、这棵树每天的增长重量
    你每天最多能砍1棵树，砍下这棵树的收益为：
    这棵树的初始重量 + 这棵树增长到这一天的总增重
    从第1天开始，你一共有m天可以砍树，返回m天内你获得的最大收益
    测试链接 : https://pintia.cn/problem-sets/91827364500/exam/problems/91827367873

    本题依然是按照某个标准排序之后，可以被01背包问题模型轻易解决

*/